Authorization Pursuant to 37 C.F.R. 1.71(e)
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The field of the present invention relates generally to content addressable memories (CAMs), and more particularly to CAM cells for constructing high-speed, large-capacity CAM arrays with full bit-wise and word-wise masking capability.
2. Related Art
A content addressable memory (CAM) is an associative memory device in which memory elements are identified (i.e. addressed) by their content, rather than by their physical location. A CAM generally includes a matrix of CAM cells arranged in rows and columns. Each CAM cell in this matrix usually includes a static memory element and comparison circuitry.
Typical uses for CAMs include pattern-matching memories for optical character recognition, and translation look-aside buffers for digital computers that employ virtual memory. In a traditional CAM, each CAM cell stores one bit of digital information in the static memory element. In some CAMs, each CAM cell employs "dual ended" logic, such that the cell makes available both a stored bit and its inverse. The static memory elements are connected with differential bit lines and a word line, thereby allowing read and write data operations. Typically, the comparison circuitry in each CAM cell is connected with separate differential compare bit lines, thus creating more flexibility in the timing of read, write and search operations.
An array of CAM cells, commonly arranged in a row, comprise a word of data. During a search operation, the CAM compares a search word (comparand) with a set of words stored within the CAM. One or more indicators associated with each word of data, commonly called match lines, produce a comparison result, which identifies the word(s) in the CAM that match the comparand. Thus a CAM usually requires more transistors and/or other circuit elements than standard Random Access Memory (RAM), but adds a "parallel processing" characteristic not found in a standard RAM.
One common use of a CAM is as a search tool for network address filtering. Network address filtering is a process for searching a router's station list for source and destination addresses and routing packets to the correct port(s). Modern telecommunication networks typically use digital packet or block type data formats as a means for dynamically routing data through a network. The advantages of such dynamically routed packetized data are well known. However, as data transfer rates continue to increase, the finite processing power available at network routers can cause communication bottlenecks, where data packets arrive faster than the router can determine where to route the incoming packets. Such bottlenecks can easily degrade the overall performance of a network.
A CAM can reduce processing bottlenecks by increasing the speed at which routing can be accomplished. Typical packet-based communication networks utilize digital "header" information at the beginning of each packet in the routing process. This header information comprises address fields defining source and destination information. Long addresses are necessary to accommodate the large number of potential addresses common in modern communication networks. These long addresses can substantially increase the time required to make routing decisions, thus requiring a fast searching technique during network address filtering. A CAM generally achieves this search performance by simultaneously comparing all entries stored in the CAM with a "comparand."
FIG. 1 is schematic block diagram illustrating a simple example of a conventional content addressable memory (CAM) utilizing dual-ended logic, with enlargements illustrating further details of a CAM cell and a CAM memory core cell. In FIG. 1, a CAM 100 is shown with only four rows and four columns, for a total of 16 CAM cells 110, whereas in most practical applications the CAM would have many more CAM cells. Each row corresponds to a word, or part of a word, of data. Each column corresponds to a bit of data from each row or word. Each CAM cell 110 in a column is coupled with a local pair of bit lines 112 (b and bn) and a local pair of compare lines 114 (k and kn). Because the CAM 100 in this example uses dual ended logic, the local pair of bit lines 112 carry differential data representing a single bit of data, and the local pair of compare lines 114 carry differential data representing a single bit of comparison data.
Each CAM cell 110 in a row is connected to a word line 116 and a match line 118. The word line 116 enables read and write access to the CAM cells 110. The match line 118 provides an output for a comparison result. The multiple match lines 118 feed into an encoder 120. Typically, the encoder 120 generates three output signals. A line designated HT is asserted high when one of the words stored in the CAM matches the comparand. A line designated AD, outputs a set of signals representing the address of the matched word. A line designated MLT is asserted high when multiple stored words match the comparand.
In some conventional designs, a priority encoder is used in place of the encoder 120. The priority encoder functions in the same way except that in addition to asserting the MLT line high when multiple stored words match the comparand, it also outputs a set of signals on the AD line representing the address of the matched word in the lowest position in the CAM. Moreover, in some conventional designs a dynamic random access memory (DRAM) or a static random access memory (SRAM) are employed in place of the encoder 120, thereby resulting in a CAM-DRAM or CAM-SRAM configuration, as is well known in the art.
CAM cell 110a in FIG. 1 is an expanded view of a single CAM cell 110, as may be found in a typical CAM. CAM cell 110a includes a CAM memory core cell 130, a "comparator block" comprising two N-channel field effect transistors (FET) 132 and 134, and a match line N-channel FET 136. The CAM memory core cell 130 has two outputs designated C and CN, which are differential outputs representing a single bit of data stored in CAM memory core cell 130. The first N-channel FET 132 connects to the positive compare line K and is gated by the output C. The second N-channel FET 134 connects to the negative compare line KN and is gated by the output CN. The output of the comparator block gates the match line N-channel FET 136, thereby transmitting a comparison result for CAM cell 110a to the match line 118 during a compare operation.
Alternative conventional designs involve transmission of a comparison result to a match line in a wired-NOR configuration. In these designs, the first N-channel FET 132 would be gated by CN, and the second N-channel FET 134 would be gated by C. The match line N-channel FET 136 remains gated by the output of the comparator block, but instead of connecting a match line input with a match line output, it connects the match line 118 with a ground. In this fashion, the match line 118 is pulled low whenever a mismatch between the stored word and the comparand occurs. This configuration results in a fast comparison, but every time there is a mismatch, the match lines must be discharged and then charged up again. For large CAMs, this configuration results in excessive power consumption.
FIG. 1 further shows an expanded view of an example of a CAM memory core cell 130a. In a typical configuration, the CAM memory core cell 130a includes a static memory element 140 and two access N-channel FETs 142 and 144. The static memory element 140 typically consists of two cross-coupled inverters.
While the CAM design represented by the CAM 100 can be used to construct relatively high-speed, large-capacity CAMs, in certain applications it may experience limitations. For example, when the CAM 100 becomes very large, the chances that multiple hits will occur during a compare operation increases. When this happens, the word data stored in the CAM 100 needs to be checked and updated, which can be a time consuming process. Without word-wise masking capability, the data in the CAM word that matched would need to be physically overwritten. Even with word-wise masking capability, it could take multiple cycles to find the right data if more than two hits occur during a compare operation.
In some CAM applications, only particular fields of the word data stored in the CAM need to be checked. For example, if the CAM is getting read requests from multiple devices, but the CAM only needs to check a certain small subset of those read requests, it requires the ability to mask out some read requests and find the particular data it cares about. In these CAM applications, the chances of multiple hits in the CAM increase significantly.
One technique for attempting to provide masking is to add a "valid bit" to each CAM cell. By adding a valid bit storage capacity to each CAM cell, selective bit-wise and word-wise comparisons are enabled. The valid bit storage capacity requires the addition of a second CAM memory core cell to the CAM cell. Multiple examples of such a design are shown in U.S. Pat. No. 6,044,005 entitled "Content Addressable Memory Storage Device." But once the second CAM memory core cell is added to the CAM cell, the CAM cell becomes significantly larger and consumes a great deal of power. When an application requires a very deep CAM, as is common in modern communications applications, the result is a large and power-hungry CAM.
In addition, the conventional schemes for implementing a match line chain do not work well for CAMs that need to operate at lower voltages. Each time the match line goes through N-channel FET 136 inside each CAM cell, a threshold and a body effect of the N-channel FET 136 need to be regenerated. Thus, the match line will not reach the power supply voltage level VDD upon a match, but will only reach a lower voltage, VDD minus a threshold and minus a body effect voltage. Devices that require deep CAMs, such as modern telecommunications equipment, are continually being designed with more restrictive power consumption constraints and thus need to operate at lower voltages. As the voltage used for running the CAM goes down, such conventional CAM designs impair performance.
It would therefore be advantageous to provide a CAM cell design and a method of pre-charge and comparison timing to solve the problems with conventional CAM design.